package arithmeticSortList2;

import fileDemo.mfile.FileUtils;

import java.util.Random;

import static utils.PrintUtil.printOneLine;

/**
 * 快速排序
 *  * leetcode :912. 排序数组
 * https://leetcode.cn/problems/sort-an-array/
 *
 * 快速排序算法
 * 快速排序之所以比较快，因为相比冒泡排序，每次交换式跳跃式的。
 * 这样总的比较和交换的次数就少了，速度自然提高了。
 * 最坏情况，仍可能是相邻的2个数进行交换。
 * 因此，快速排序的最差时间复杂度和冒泡排序是一样的都是Ο(n²)
 * 它的平均时间复杂度为（O(nlogn)），
 * 快速排序是基于二分的思想。
 * <p>
 * 在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。
 * 事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
 * <p>
 * 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）
 * <p>
 * 算法步骤：
 * 1 从数列中挑出一个元素，称为 "基准"（pivot），
 * <p>
 * 2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 * 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
 * <p>
 * 3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 * 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。
 * 虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
 * <p>
 * 分析：
 * 快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。
 * 但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。
 * 为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。
 * 快速排序是一个不稳定的排序方法。
 * <p>
 *
 * @author zybw-kf01
 */
public class QuickSortDemo2 {
    public static void main(String[] args) {
        String [] str =  FileUtils.readFile2String("./src/arithmeticSortList2/QuickSort_Test_Data.txt").split(",");
        int [] numbers = new int[str.length];
        for (int i = 0; i < str.length; i++) {
            numbers[i] = Integer.parseInt(str[i]);
        }
//        int[] numbers = {0, 20, 6, 10, 0, 6, 7, 2, 1, -5, 15, 55};
//        int[] numbers = {2, 8, 7, 23, 34, 67, 45, 30, 56, 34, 21, 34, 67, 8, 5};

        System.out.println("排序前：len:" + numbers.length);
        printOneLine(numbers);
//        quickSort(numbers, 0, numbers.length - 1);
//        sort(numbers, 0, numbers.length - 1);
        quickSortMidTarget(numbers, 0, numbers.length - 1);
        System.out.println("排序后");
        printOneLine(numbers);
    }

    //通过 leetcode,但是时间太长。 2024 年 04 月 09 日 10:32:46
    private static void quickSort1(int[] data, int left, int right) {
        if (data == null) return;
        if (left >= right) return;

        int target = data[left];// 目标值 ,中轴的值
        int originLeft = left,originRight = right;
        while (left < right) {
            while (target < data[right] && left < right) {//直到 遇到 target>= data 的数据。或者 相遇
                right--;
            }
            while (target >= data[left] && left < right) {//直到 遇到 target< data 的数据。或者 相遇
                left++;
            }
            if (left < right) {// 左右 互换，
                int temp = data[left];
                data[left] = data[right];// 比中轴小的记录移到低端
                data[right] = temp;// 比中轴大的记录移到高端
            }
        }
        //left right 碰到一个点。这个点与 target 交换, 这个值 data<=target ,因为右边先移动 <--.
        data[originLeft] = data[left]; // 中轴记录到尾
        data[left] = target;

        // 得到left 中轴位置
        quickSort(data, originLeft, left - 1);//中轴 左边排序
        quickSort(data, left + 1, originRight);//中轴 右边排序
//        quickSort(data, originLeft, right - 1);//中轴 左边排序
//        quickSort(data, right + 1, originRight);//中轴 右边排序
    }

    //通过 leetcode, 与上面的不同。仅仅，target ,改到了中间，然后交换到左边。---继续。
    private static void quickSortMidTarget1(int[] data, int left, int right) {
        if (data == null) return;
        if (left >= right) return;

//        int target = data[left];// 目标值 ,中轴的值
        int targetIndex = (right - left) / 2 + left;
        int target = data[targetIndex];// 目标值 ,中轴的值
        swip(data,targetIndex,left);

        int originLeft = left,originRight = right;
        while (left < right) {
            while (target < data[right] && left < right) {//直到 遇到 target>= data 的数据。或者 相遇
                right--;
            }
            while (target >= data[left] && left < right) {//直到 遇到 target< data 的数据。或者 相遇
                left++;
            }
            if (left < right) {// 左右 互换，
                int temp = data[left];
                data[left] = data[right];// 比中轴小的记录移到低端
                data[right] = temp;// 比中轴大的记录移到高端
            }
        }
        //left right 碰到一个点。这个点与 target 交换, 这个值 data<=target ,因为右边先移动 <--.
        data[originLeft] = data[left]; // 中轴记录到尾
        data[left] = target;

        // 得到left 中轴位置
        quickSortMidTarget1(data, originLeft, left - 1);//中轴 左边排序
        quickSortMidTarget1(data, left + 1, originRight);//中轴 右边排序
//        quickSort(data, originLeft, right - 1);//中轴 左边排序
//        quickSort(data, right + 1, originRight);//中轴 右边排序
    }
    public static void swip(int[] numbers,int l,int r){
        int temp = numbers[l];
        numbers[l] = numbers[r];
        numbers[r] = temp;
    }



    //通过 leetcode 啥时间太长。与 上面 【quickSort1】 写法一样，只不过拆分成了 2 个方法。
    public static void quickSort(int[] numbers, int low, int high) {
        if (numbers == null || numbers.length == 0) return; // 查看数组是否为空
        if (low < high) {
            int middle = getMiddle(numbers, low, high); // 将numbers数组进行一分为二
            quickSort(numbers, low, middle - 1); // 对低字段表进行递归排序
            quickSort(numbers, middle + 1, high); // 对高字段表进行递归排序
        }
    }
    /**
     * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
     *
     * @param numbers 带查找数组
     * @param low     开始位置
     * @param high    结束位置
     * @return 中轴所在位置
     */
    public static int getMiddle(int[] numbers, int low, int high) {
        int temp = numbers[low]; // 数组的第一个作为中轴
        int base = low;
        while (low < high) {
            //todo 需要修改对应的
            // numbers[high] > temp 对应 numbers[low] <= temp
            // numbers[high] >= temp 对应 numbers[low] < temp
            while (low < high && numbers[high] > temp) {
                high--;
            }
            while (low < high && numbers[low] <= temp) {
                low++;
            }
            if (low < high && (numbers[low] != numbers[high])) {
                int tempLow = numbers[low];
                numbers[low] = numbers[high];// 比中轴小的记录移到低端
                numbers[high] = tempLow; // 比中轴大的记录移到高端
            }
        }
        //这个点与 base 交换,
        numbers[base] = numbers[low];//最低点=比中轴小的值，  low移动到了重点
        numbers[low] = temp;// 中轴的值=base,低点 已经移动到中轴位置。

        return low; // 返回中轴的位置
    }



    //TODO target 在中间，而不是左边。这样快。。。通过 leetcode 2024-01-19 17:55:46 练习  最快。Hoare
    public static void quickSortMidTarget(int[] data, int left, int right) {
        if (data == null || left >= right || left < 0 || right >= data.length) return;
        int pivotNotMid = getTarget(data, left, right);
        quickSortMidTarget(data, left, pivotNotMid );//对应了 return right.
        quickSortMidTarget(data, pivotNotMid + 1, right);
    }
    private static int getTarget(int[] data, int left, int right) {
        if (left >= right) return -1;
        int target = data[left+(right-left)/2];

        while (true) {
            while (data[left] < target) left++;//get first leftIndex that >= target
            while (data[right] > target) right--;//get first rightIndex that <= target

            //TODO meet,,  left >= right...   return index of target
            if (left >= right) return right;//TODO left error!!!!

            //swap,left right...  left < target < right
            if (data[left] != data[right]){//减少交换次数。 同样的值不交换。
                int temp = data[right];
                data[right] = data[left];
                data[left] = temp;
            }

            left++;//move to next, for next loop
            right--;//move to next, for next loop
        }
    }



    //随机 target    作者：力扣官方题解：https://leetcode.cn/problems/sort-an-array/solutions/178305/pai-xu-shu-zu-by-leetcode-solution/
    class Solution {
        public int[] sortArray(int[] nums) {
            randomizedQuicksort(nums, 0, nums.length - 1);
            return nums;
        }

        public void randomizedQuicksort(int[] nums, int l, int r) {
            if (l < r) {
                int pos = randomizedPartition(nums, l, r);
                randomizedQuicksort(nums, l, pos - 1);
                randomizedQuicksort(nums, pos + 1, r);
            }
        }

        public int randomizedPartition(int[] nums, int l, int r) {
            int target = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
            swap(nums, r, target);//target 移动到末尾
            return partition(nums, l, r);
        }

        public int partition(int[] nums, int l, int r) {
            int pivot = nums[r];
            int i = l - 1;
            for (int j = l; j <= r - 1; ++j) {
                if (nums[j] <= pivot) {
                    i = i + 1;
                    swap(nums, i, j);
                }
            }
            swap(nums, i + 1, r);
            return i + 1;
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

}
